package cn.rocky.structures.bloom_filter;

import java.util.BitSet;

/**
 * 布隆过滤器:基于数组和哈希函数散列元素的结构,很像HashMap的哈希桶。
 * 布隆过滤器可以用于检测一个元素是否在集合中。
 * 它的优点是空间效率和查询时间比一般算法要好很多,但也有一定概率的误判性。如HashMap出现哈希碰撞
 * 实现条件: 包括存放二进制元素的BitSet以及多样性的哈希计算函数
 *
 * 1.布隆过滤器的使用场景？
 * 2.布隆过滤器的实现原理和方式？
 * 3.如何提高布隆过滤器的准确性？
 * 4.有哪些中哈希计算方式？
 * 5.都有哪些类型的布隆过滤器实现？Google 开源的 Guava 中自带的布隆过滤器、Redis 中的布隆过滤器(https://github.com/RedisBloom/RedisBloom (opens new window))
 */
public class BloomFilter {


    private static final HashGenerator.HashGroup[] GROUPS = new HashGenerator.HashGroup[]{HashGenerator.HashGroup.G1, HashGenerator.HashGroup.G2, HashGenerator.HashGroup.G3, HashGenerator.HashGroup.G4};

    private final BitSet bits;

    private HashGenerator[] generators;

    /**
     * 构造函数时根据所需创建的容器大小和哈希种子来初始化布隆过滤器
     * @param size
     * @param seeds
     */
    public BloomFilter(int size, int[] seeds) {
        bits = new BitSet(size);
        generators = new HashGenerator[seeds.length];
        for (int i = 0; i < seeds.length; i++) {
            generators[i] = new HashGenerator(size, seeds[i],GROUPS[i % GROUPS.length]);
        }
    }

    /**
     * 存放元素
     */
    public void add(String value) {
        for (HashGenerator generator : generators) {
            int hash = generator.doHash(value);
            bits.set(hash, true);
        }
    }

    /**
     * 对比元素
     */
    public boolean contains(String value) {
        boolean ret = true;
        for (HashGenerator generator : generators) {
            ret = ret && bits.get(generator.doHash(value));
        }
        return ret;
    }

    /**
     * 哈希工具
     */
    public static class HashGenerator {

        private int size;

        private int seed;

        private HashGroup group;

        enum HashGroup {
            G1,G2,G3,G4
        }

        public HashGenerator(int size, int seed, HashGroup group) {
            this.size = size;
            this.seed = seed;
            this.group = group;
        }

        public int doHash(String value) {
            switch (group) {
                case G1 :
                    return hashG1(value);
                case G2 :
                    return hashG2(value);
                case G3 :
                    return hashG3(value);
                case G4 :
                    return hashG4(value);
                default :
                    throw new RuntimeException("Err HashGroup Is null");
            }
        }


        private int hashG1(String value) {
            int hash = 0;
            for (int idx = 0; idx < value.length(); idx++) {
                char c = value.charAt(idx);
                hash = (hash << 5) + hash + c;
                hash &= hash;
                hash = Math.abs(hash);
            }
            return hash % (seed * size - 1);
        }

        private int hashG2(String value) {
            int hash = 7379;
            for (int idx = 0; idx < value.length(); idx++) {
                char c = value.charAt(idx);
                hash = (hash << 5) + hash + c;
            }
            return Math.abs(hash % seed * (size - 1));
        }

        private int hashG3(String value) {
            int hash = 0;
            for (int idx = 0; idx < value.length(); idx++) {
                char c = value.charAt(idx);
                hash = (hash << 5) + hash + c;
                hash += c;
                hash &= hash;
            }
            return Math.abs(hash % (seed * size - 1));
        }

        private int hashG4(String value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (size - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }

    public static void main(String[] args) {
        String val00 = "小傅哥";
        String val01 = "https://bugstack.cn";
        String val02 = "https://github.com/fuzhengwei/CodeGuide";
        String val03 = "https://github.com/fuzhengwei";
        BloomFilter filter = new BloomFilter(Integer.MAX_VALUE, new int[]{7, 19, 43, 77});
        filter.add(val00);
        filter.add(val01);
        filter.add(val02);
        System.out.println("测试结果 val00："+ val00 +" 布隆过滤器："+filter.contains(val00));
        System.out.println("测试结果 val01："+ val01 +" 布隆过滤器："+filter.contains(val01));
        System.out.println("测试结果 val02："+ val02 +" 布隆过滤器："+filter.contains(val02));
        System.out.println("测试结果 val03："+ val03 +" 布隆过滤器："+filter.contains(val03));
    }
}
